package P1线性结构;
//中缀转后缀
public class InfixToSuffix {
    public static void main(String[] args) {
        String expression = "(10+20/2*3)/2+8";
        ArrayList<String> suffixList = infixToSufix(expression);
        System.out.println(suffixList);
        //后缀表达式的计算
        int result = evalue(suffixList);
        System.out.println(result);
    }
    //后缀表达式的计算过程
    private static int evalue(ArrayList<String> suffixList) {
        ArrayStack<Integer> stack = new ArrayStack<>();
        for (String token : suffixList) {
            if (isOperator(token)) {
                process(stack, token);
            } else {
                stack.push(new Integer(token));
            }
        }
        return stack.pop();
    }

    private static void process(ArrayStack<Integer> stack, String token) {
        int num1 = stack.pop();
        int num2 = stack.pop();
        if (token.equals("+")) {
            stack.push(num2 + num1);
        } else if (token.equals("-")) {
            stack.push(num2 - num1);
        } else if (token.equals("*")) {
            stack.push(num2 * num1);
        } else {
            stack.push(num2 / num1);
        }
    }

    private static boolean isOperator(String token) {
        return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
    }

    private static ArrayList<String> infixToSufix(String expression) {
        ArrayStack<String> stack = new ArrayStack<>();
        ArrayList<String> list = new ArrayList<>();
        expression = format(expression);
        String[] tokens = expression.split(" ");
        for (String token : tokens) {
            if (token.length() != 0) {
                if (token.equals("+") || token.equals("-")) {
                    while (!stack.isEmpty() && !stack.peek().equals("(")) {
                        list.add(stack.pop());
                    }
                    stack.push(token);
                } else if (token.equals("*") || token.equals("/")) {
                    while (!stack.isEmpty() && (stack.peek().equals("*") || stack.peek().equals("/"))) {
                        list.add(stack.pop());
                    }
                    stack.push(token);
                } else if (token.equals("(")) {
                    stack.push("(");
                } else if (token.equals(")")) {
                    while (!stack.peek().equals("(")) {
                        list.add(stack.pop());
                    }
                    stack.pop();
                } else {
                    list.add(token);
                }
            }
        }
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }
    private static String format(String expression) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')') {
                sb.append(' ');
                sb.append(c);
                sb.append(' ');
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
